- Sorting (Case study #2)

Input:
2	5	10	1
Objective: Sort the elements of the array in an ascending order

Output:
1	2	5	10

2	5	10	1

Bubble sort (very had to implement)
1. Selection Sort:
Application#1: SortingApp.java
arr:
2	5	10	1

1	2	5	10

2	5	10	1
1	5	10	2
1	2	10	5
1	2	5	10

Divide and conquer:
Create a simpler version of the problem
Simpler version of the problem: Let the smallest value occupy the first position of the array

for(int idx = 0; idx < array.length - 1; idx++) {
int idxMin = idx;
for(int scan = idx + 1; scan < arr.length; scan++) {
	if(array[scan] < array[idxMin]) {
		idxMin = scan;
	}
}

// swap the values within the array at indexes idx and idxMin
swap(arr, idx, idxMin);
}

n - 1 + n - 2 + ... + 1 = n * (n-1) / 2 = proportion to n^2
in O(n log2(n))

2. Insertion sort

10	5	2	1

1	2	5	10

Divide and conquer

for(int idx = 1; idx < arr.length; idx++) {
int insert = idx;
while(insert > 0 && arr[insert] < arr[insert - 1]) {
	swap(arr, insert, insert - 1);
	insert--;
}
}

3. BubbleSort: BubbleSort.java

4. Anagrams
Same set of characters + same frequencies
abc
bca
cab

aac
ac












